package club.babyf.nativeai.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * LRUCache.
 *
 * @author zhanglei.
 * @date 2025/7/20 22:16.
 * @description 实现LRU缓存.
 */
public class _22_LRUCache {

    /**
     * 双向链表节点类
     */
    static class Node {

        int key;

        int value;

        Node prev;

        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

    }

    /**
     * 哈希表用于快速查找节点
     */
    private final Map<Integer, Node> cacheMap = new HashMap<>();

    /**
     * 缓存容量
     */
    private final int capacity;

    /**
     * 链表头尾哨兵节点（简化边界处理）
     */
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    public _22_LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取缓存值
     *
     * @param key key
     * @return value
     */
    public int get(int key) {
        if (!cacheMap.containsKey(key)) {
            // 键不存在
            return -1;
        }
        Node node = cacheMap.get(key);
        // 移动到头部表示最近使用
        moveToHead(node);
        return node.value;
    }

    /**
     * 添加或更新缓存
     *
     * @param key   key
     * @param value value
     */
    public void put(int key, int value) {
        if (cacheMap.containsKey(key)) {
            Node node = cacheMap.get(key);
            // 更新值
            node.value = value;
            // 移动到头部
            moveToHead(node);
            return;
        }

        // 创建新节点
        Node newNode = new Node(key, value);
        // 加入哈希表
        cacheMap.put(key, newNode);
        // 添加到链表头部
        addToHead(newNode);

        // 检查容量，删除尾部节点（LRU）
        if (cacheMap.size() > capacity) {
            Node lruNode = removeTail();
            cacheMap.remove(lruNode.key);
        }
    }

    /**
     * 将节点添加到链表头部
     *
     * @param node 节点
     */
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 从链表中移除节点
     *
     * @param node 节点
     */
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 移动节点到链表头部
     *
     * @param node 节点
     */
    private void moveToHead(Node node) {
        // 从原位置移除
        removeNode(node);
        // 添加到头部
        addToHead(node);
    }

    /**
     * 添加到头部
     *
     * @return 节点
     */
    private Node removeTail() {
        // 尾部哨兵的前一个节点
        Node lruNode = tail.prev;
        removeNode(lruNode);
        return lruNode;
    }

    public static void main(String[] args) {
        // 容量为2
        _22_LRUCache cache = new _22_LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        // 返回 1
        System.out.println(cache.get(1));
        // 淘汰 key 2
        cache.put(3, 3);
        // 返回 -1 (未找到)
        System.out.println(cache.get(2));
        // 淘汰 key 1
        cache.put(4, 4);
        // 返回 -1
        System.out.println(cache.get(1));
        // 返回 3
        System.out.println(cache.get(3));
        // 返回 4
        System.out.println(cache.get(4));
    }

}
